package _01_动态数组;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class _229_求众数II {

    public static void main(String[] args) {

        _229_求众数II v = new _229_求众数II();

        int[] ins = {1, 2};
        System.out.println(v.majorityElement(ins));

    }

    // hash计数法则
    public List<Integer> majorityElement1(int[] nums) {
        List<Integer> list = new ArrayList<>();
        Map<Integer, Integer> map = new HashMap<>();

        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        // 计算大于3/n的数
        int num = nums.length / 3;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue() > num) {
                list.add(entry.getKey());
            }
        }
        return list;
    }

    // 摩尔投票法则, 遇到不同的就相减
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> list = new ArrayList<>();

        int ele1 = 0;
        int ele2 = 0;
        int count1 = 0;
        int count2 = 0;
        for (int cur : nums) {
            if (count1 > 0 && ele1 == cur) {
                count1++;
            } else if (count2 > 0 && ele2 == cur) {
                count2++;
            } else if (count1 == 0) {
                ele1 = cur;
                count1++;
            } else if (count2 == 0) {
                ele2 = cur;
                count2++;
            } else {
                count1--;
                count2--;
            }
        }

        // 计算当前获得的值是否大于3/n
        int ans1 = 0;
        int ans2 = 0;
        for (int num : nums) {
            if (num == ele1) {
                ans1++;
            } else if (num == ele2) {
                ans2++;
            }
        }
        int target = nums.length / 3;
        if (ans1 > target) list.add(ele1);
        if (ans2 > target) list.add(ele2);
        return list;
    }

}
